The system and method described herein relates generally to the field of testing, and more particularly, to developing testing configurations for compatibility testing.
In today""s world, intense competition in many industries places significant pressure on companies and their employees to both reduce product development and testing cycle times, while at the same time many products are increasing in complexity. Further, in many industries the trend has been a demand from customers for companies to provide wide ranges of choices for customers, such as to allow customers the ability to select one particular type of component from a choice of many, for each of several different components present in a product. For example, in the computer industry customers may wish to purchase a computer system, but specify, for example, the specific type of central processing unit (CPU) the system will include, the amount of memory, different types of software, and many other features.
When multiple variations of multiple components can be selected companies must, to the best of their ability, test each possible combination to ensure that the different components are compatible with one another, and that the system will function satisfactorily with that particular selection of components. When the number of selections is not too large, testing each combination may be possible. However, where the number of configurations is large, testing of each configuration of components is neither possible nor practical. Under these circumstances, an efficient system and method for selecting a reasonable number of configurations is desired such that the maximum number of combinations of components can be examined with minimum number of tests or trials.
In the context of testing compatibility, whether in the computer industry or otherwise, the result of any test is either pass or fail rather than a quantitative result. Under these circumstances confounding effect is of no interest, as is the case when there are multiple variables and a quantitative result is sought. Thus, when designing configuration tests, the objective is to select a minimum set of configurations that will examine the greatest number of combinations of components, thus avoiding redundancy and at the same time avoiding holes in the test space, thereby increasing test efficiency.
By maximizing the coverage there is a better chance to achieve a greater number of failures. For example, if three different selections are available for each of two different components (selection 1, 2 or 3 for the first component and selection A, B or C for the second component), there are a total of six different variables and nine possible combinations. In configuration testing, the components are referred to as xe2x80x9cfactorsxe2x80x9d while the selections are referred to as xe2x80x9clevels.xe2x80x9d It is most desirable to ensure that each of the six different levels appear in at least one test. If this occurs, there will be 100% coverage for each level taken individually, and after completing the testing it will be known with certainty whether each level, taken alone, will cause the system as a whole to fail.
The second level of coverage is every conceivable combination of two variables, i.e., 1A; 1B; 1C; 2A; 2B; 2C, 3A; 3B; and 3C. 100% coverage would ensure that any combination of two will be covered in the trials. Although with large numbers of configurations 100% coverage at the first, second, and all subsequent levels is not possible, the objective is most importantly to maximize coverage at the first level, second most importantly to maximize coverage at the second level, and so on.
In developing testing configurations, matrices are often used in which individual columns represent the possible factors, rows represent the number of trials, and the entries in the matrix represent the combination of levels (the xe2x80x9clevel combinationxe2x80x9d) for any given trial. For example, for a system that includes two factors (F1, F2) each of which have two levels (L1, L2), a testing matrix could be as follows:
For factors having two levels, entries in the matrix can be replaced by 1""s or 0""s to provide the following matrix:
where 0 represents L1 and 1 represents L2. Note that all possible combinations can be covered (100% coverage) in four trials. In choosing how to populate a testing matrix the objective in configuration testing is to populate the matrix in such a way that coverage is maximized for the number of trials.
In achieving this objective of maximizing coverage, the principle of orthogonality is always important. An orthogonal array is an array of 1""s and 0""s that for strength n has the property that for any n number of columns selected all possible combinations of 1""s and 0""s will appear an equal number of times. For example, for an orthogonal array of strength 2, when selecting any two columns all possible combinations of 1""s and 0""s (00, 01, 10, and 11) will appear an equal number of times. Thus, an orthogonal array of strength n not only helps ensure that certain combinations of variables are not disproportionately tested, but also ensures 100% coverage for any combination of n different variables. Degradation of orthogonality for any testing matrix represents an imbalance in the variables represented in the trials and, therefore, can cause less than desirable coverage. Thus, it is desirable to maintain orthogonality of the highest strength in a testing matrix for the least number of trials.
A well known limitation of orthogonal arrays, however, is that orthogonal arrays of size 2n can have only n+1 independent orthogonal arrays of strength n. For example, to maintain a strength of 3 (n=3), an orthogonal array of vector size 8 (23) can have only 4 (3+1) columns. In other words, for only 4 columns will the property hold true that in any 3 out of the 4 columns all possibilities of 1""s and 0""s (000, 001, 010, 100, 011, 101, 110, and 111) will appear an equal number of times. In testing configuration matrices, 4 columns represents only four bi-level factors. It would, of course, be desirable to maintain orthogonality across a larger number of factors for the same number of trials.
In developing configuration testing matrices, it has been discovered that Hadamard matrices are useful in populating the matrix, particularly for pass/fail testing applications. Hadamard matrices are square matrices of order n whose entries are (+)""s and (xe2x88x92)""s. If we replace (+) with 1 and (xe2x88x92) with 0 they will be orthogonal arrays of strength two, that have the property HHxe2x80x2=nI, where I is an identity matrix. Thus, for any one column or for any two columns in a Hadamard matrix, any given combination of 1""s and 0""s will appear an equal number of times. Hadamard matrices can easily be used for factors having only two levels since each level can be represented by either a 0 or a 1.
More recently, it has been shown that Hadamard matrices can also be used for variables having more than two levels by combining columns. For example, for a variable having four levels, each level can be represented by the combinations 00, 01, 10, and 11. By combining two columns in the Hadamard matrix each of these combination can be represented. See xe2x80x9cPass/Fail Functional Testing and Associated Test Coverage,xe2x80x9d Breyfogle, R. W., Quality Engineering 4(2), 1991, pp. 227-234. Combining columns of the Hadamard matrix, particularly in a random fashion, results in degradation of the orthogonal properties of the Hadamard matrix particularly when, for any array size of 2n, there are more than n+1 columns (more than n+1 factors).
Another disadvantage of combining columns to account for variables having greater than two levels occurs when the number of levels is not a power of two. For example, for a variable having three levels, those three levels can be represented by 00, 01 and 10, leaving the combination 11 unassigned. Breyfogle teaches that when this unassigned combination is encountered in the Hadamard matrix, the value entered into the corresponding configuration testing matrix that is to be populated should either be randomly assigned to one of the assigned levels, or sequentially assigned to the first level (00) the first time it appears, to the second level the second time it appears, and so on. Such random or sequential assignment is disadvantageous in that it does not contribute in any way toward the objective of maximizing coverage.
In accordance with the teachings herein, a new system and method are disclosed for constructing configuration testing matrices that reduces and/or eliminates the disadvantages associated with presently known methods. Such a system and method enables the number of columns to be increased while maintaining orthogonality, and improves coverage percentages. In addition, a new system and method is provided for replacing unassigned variables and exceptions in an integer matrix in a manner that improves coverage percentages.
More particularly, according to one embodiment, a method for developing testing configurations is provided including the steps of identifying factors to be tested and levels for each factor, selecting a Hadamard matrix of an appropriate size such that for any integer 1, 2 . . . n, the Hadamard matrix has a size 2n and (2nxe2x88x921) columns, and maintains orthogonality of strength n when columns are selected sequentially, and creating a configuration matrix from the selected Hadamard matrix.
In another embodiment the creating step further includes the steps of first creating an integer matrix from the Hadamard matrix by assigning different columns of the Hadamard matrix to represent different factors, wherein for factors having more than two levels a number X of consecutive columns of the Hadamard matrix is assigned to the factors such that X is the smallest integer for which (2Xxe2x89xa7the number of levels) for that factor, and for each factor assigning a level index. The method further includes the step of inserting in a corresponding column and row of the integer matrix the level index assigned to the binary codes appearing in the Hadamard matrix.
In yet another embodiment, the creating step further includes the step of inserting an indicator in the integer matrix for each binary code appearing in the Hadamard matrix that is not assigned to a level index.
In yet another embodiment, the integer matrix is an initial integer matrix, and the creating step further includes the step of replacing indicators in the initial integer matrix with assigned level indexes for the corresponding factor, wherein said initial integer matrix becomes a final integer matrix when all such indicators have been replaced.
In yet another embodiment, the replacing step further includes the steps of, for each row in the initial integer matrix having an indicator, replacing that row with a possible replacement level combination in a manner that improves testing coverage.
In yet another embodiment, the step of replacing in a manner that improves coverage further includes the step of determining a subset of all possible replacement level combinations for the row having the indicator. In a further embodiment, the step of replacing in a manner that improves coverage further includes the steps of obtaining a frequency matrix count for each possible replacement level combination, and selecting from the subset each possible replacement level combination having the lowest frequency matrix count. If more than one is selected then, according to yet another embodiment, the step of replacing in a manner that improves coverage further includes the steps of obtaining a proportionality matrix count for each selected possible replacement level combination, and choosing each possible replacement level combination having the lowest proportionality matrix count. If there is more than one chosen possible replacement level combination, then according to one embodiment, the replacing step further includes the step of choosing a single one of the chosen possible replacement level combinations having the lowest proportionality matrix count.
In yet another embodiment, the step of replacing in a manner that improves coverage further includes the step of replacing the row of the initial integer matrix with the selected or chosen possible replacement level combination.
In yet another embodiment, the method for developing testing configurations further includes the steps of calculating coverages based on the final integer matrix, and creating a coverage matrix containing the calculated coverages.
In yet another embodiment, the step of replacing in a manner that improves coverage further includes the steps of removing all excluded level combinations from the subset of possible replacement level combinations and determining if the subset is empty. In yet another embodiment, if the subset is determined to be empty, the replacing step further includes the step of replacing an assigned level index in the row of the initial integer matrix with an indicator.
A computer system is also provided having a processor, memory, an input device, and a configuration generator tool application for developing testing configurations. The configuration generator tool is executable by the computer system, and is operable to receive input data including a number of factors to be tested and levels for each factor from a user through the input device. The configuration generator tool is further operable to select from a group of Hadamard matrices stored in memory a Hadamard matrix of an appropriate size such that for any integer 1, 2 . . . n, the Hadamard matrix has a size 2n and (2nxe2x88x921) columns, and maintains orthogonality of strength n when columns are selected sequentially. The configuration generator tool is further operable to create a testing configuration matrix from the selected Hadamard matrix.
In another embodiment, the configuration generator tool is further operable to create the testing configuration matrix by first creating an integer matrix from the Hadamard matrix by assigning different columns of the Hadamard matrix to represent different factors, wherein for factors having more than two levels a number X of consecutive columns of the Hadamard matrix is assigned to the factors such that X is the smallest integer for which (2Xxe2x89xa7the number of levels) for that factor, and further assigning a level index to each factor, and inserting in a corresponding column and row of the integer matrix the level index assigned to the binary codes appearing in the Hadamard matrix.
In yet another embodiment, the configuration generator tool is further operable to create the testing configuration matrix by inserting an indicator in the integer matrix for each binary code appearing in the Hadamard matrix that is not assigned to a level index.
In yet another embodiment, the integer matrix is an initial integer matrix, and the configuration generator tool is further operable to create the testing configuration matrix by replacing indicators in the initial integer matrix with assigned level indexes for the corresponding factor, wherein the initial integer matrix becomes a final integer matrix when all such indicators have been replaced.
In yet another embodiment, the configuration generator tool is further operable to create the testing configuration matrix by, for each row in the initial integer matrix, having an indicator, replacing the row having an indicator with a possible replacement level combination in a manner that improves testing coverage.
In yet another embodiment, the configuration generator tool is further operable to replace the row having an indicator in a manner that improves coverage by determining a subset of all possible replacement level combinations for that row. In yet another embodiment the configuration generator tool is further operable to replace the row in a manner that improves coverage by obtaining a frequency matrix count for each possible replacement level combination; and selecting each possible replacement level combination having the lowest frequency matrix count. According to yet another embodiment, if more than one possible replacement level combination is selected, then the configuration generator tool is further operable to perform the replacing step by obtaining a proportionality matrix count for each selected possible replacement level combination, and choosing each possible replacement level combination having the lowest proportionality matrix count. In yet another embodiment, if more than one possible replacement level combinations are chosen, the configuration generator tool is further operable to perform the replacing step by choosing a selected one of the chosen possible replacement level combinations, and, in yet another embodiment, to replace the row of the initial integer matrix with the selected or chosen possible replacement level combination.
In yet another embodiment, the configuration generator tool is further operable to update the frequency and proportionality matrices.
In yet another embodiment, the configuration generator tool is further operable to calculate coverages based on the final integer matrix, and create a coverage matrix containing the calculated coverages.
In yet another embodiment, the configuration generator tool is further operable to receive input data including excluded level combinations, and to replace each row of said initial integer matrix containing excluded level combinations in a manner that improves testing coverage.
According to yet another embodiment, a method of developing testing configurations is provided including the steps of identifying factors to be tested and levels for each factor, selecting a Hadamard matrix of an appropriate size and creating an initial integer matrix from the selected Hadamard matrix by assigning different columns to represent different factors, wherein for factors having more than two levels a number X of consecutive columns of the Hadamard matrix is assigned to the factors such that X is the smallest integer for which (2Xxe2x89xa7the number of levels) for that factor, and for each factor assigning a level index. The method further includes the steps of inserting in a corresponding column and row of the integer matrix the level index assigned to the binary codes appearing in the Hadamard matrix, and using a frequency matrix and a proportionality matrix to replace each row of said initial integer matrix having an indicator in a manner that improves testing coverage.